/**
 * @param {number[][]} forest
 * @return {number}
 */
export var cutOffTree = function (forest) {
  let ans = 0
  // 1. 找到所有树的位置
  const trees = [] // 记录树的[高度，row，col]
  for (let i = 0; i < forest.length; i++) {
    for (let j = 0; j < forest[0].length; j++) {
      if (forest[i][j] > 1) {
        trees.push([forest[i][j], i, j])
      }
    }
  }
  // 2. 按照高度排序
  trees.sort((a, b) => a[0] - b[0])
  // 3. 从起点开始，计算每个树之间的最短距离
  let from = [0, 0]
  for (let i = 0; i < trees.length; i++) {
    const to = [trees[i][1], trees[i][2]]
    const step = bfs(forest, from, to)
    if (step === -1) return -1
    ans += step
    from = to
  }
  return ans
}

function bfs(forest, from, to) {
  if (from[0] === to[0] && from[1] === to[1]) return 0
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]
  const visited = new Array(forest.length).fill(0).map(() => new Array(forest[0].length).fill(0))
  const queue = [from]
  let step = 0
  visited[from[0]][from[1]] = 1
  while (queue.length) {
    step++
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const [row, col] = queue.shift()
      for (const dir of dirs) {
        const [nextRow, nextCol] = [row + dir[0], col + dir[1]]
        if (nextRow === to[0] && nextCol === to[1]) return step
        if (
          nextRow < 0 ||
          nextRow > forest.length - 1 ||
          nextCol < 0 ||
          nextCol > forest[0].length - 1 ||
          visited[nextRow][nextCol] === 1 ||
          forest[nextRow][nextCol] === 0
        )
          continue
        visited[nextRow][nextCol] = 1
        queue.push([nextRow, nextCol])
      }
    }
  }
  return -1
}
